package com.kznnc.data_structure.sort.one;

public class GuibingSort {

    public static void main(String[] args) {
        int[] data = {9, 5, 6, 8, 0, 3, 7, 1};
        int right = data.length - 1;
        split(data, 0, right);
    }


    public static void split(int[] data, int left, int right) {
        // 相等的时候就表示只有一个数了 不用再拆了
        if (left < right) {
            int mid = (left + right) / 2;
            split(data, left, mid);
            split(data, mid + 1, right);
            // 分完后就要进行合并后了  也就是我们递归里面的归
            mergeSort(data, left, mid, right);
        }
    }

    public static void mergeSort(int[] data, int left, int mid, int right) {
       // 借助一个临时数组用来保存合并的数据
        int[] temp = new int[data.length];

        // 表示的是左边的第一个数的位置
        int point1 = left;
        // 表示的是右边的第一个数的位置
        int point2 =mid+1;
        // 表示的是 我们当前到了那个问题位置了
        int loc = left;

        // 利用插入算法的思想  按从小到大排序 将右边的数插入到左边
        while (point1<= mid && point2 <= right){
          if (data[point1] < data[point2]){
              temp[loc] = data[point2];
              point1++;
              loc++;
          }else {
              temp[loc] = data[point2];
              point2++;
              loc++;
          }
        }

        // 处理没有合并完的数据
        // 为什么会有没有合并完的数据?
        while (point1<= mid){
            temp[loc++] = data[point1++];
        }
        while (point2 <= right){
            temp[loc++] = data[point2++];
        }

        for (int i = left; i <right ; i++) {
            data[i] = temp[i];
        }

    }
}
